Our proof follows the framework
of~\cite{ChenDengTeng06,ChenDengTeng08} for proving the hardness of
approximating Nash equilibria in 2-player games.  This framework
starts with a high-dimensional discrete fixed point problem, \brouwer,
which is also \textbf{PPAD}-complete.  The input to \brouwer\ is a Boolean
circuit that assigns a color from $\{ 1,...,n,n+1\}$ to each interior
node of an $n$-dimensional grid $\{0,1,...,8\}^n$.  This grid has
about $2^{3n}$ cells, each of which is an $n$-dimensional hypercube.
The discrete fixed point is defined to be a panchromatic simplex
inside a hypercube.  This framework
of~\cite{ChenDengTeng06,ChenDengTeng08} uses a new geometric condition
for discrete fixed points, which requires that the average of $n^3$
sampled points in the interior of the targeted panchromatic simplex is
inverse-polynomially close to the zero vector.  The rest of the proof
follows the framework of~\cite{DaskalakisGoldbergPapadimitriou06}.

Our broad definition of an $\epsilon$-equilibrium poses additional
technical challenges which did not occur in the reductions of
~\cite{ChenDengTeng06,ChenDengTeng08}.  In particular, in the
presence of errors, our Boolean gadgets only approximately simulate
the Boolean operations, while in previous reductions, the Boolean
gadgets are precise. We prevent magnification of errors in the Boolean simulation by strategically adding a LESS gadget to correct errors after each logic step.

We focus on bounding the errors
for the gadgets of Theorem~\ref{thm:exact} and the addition of the extra LESS gadgets.  Other details closely match those
of~\cite{ChenDengTeng06,ChenDengTeng08,DaskalakisGoldbergPapadimitriou06}.

Let $\epsilon_l$ (the measure of the fragility of our LESS gadget) be
a real number such that $\epsilon \le \epsilon_l^3$.  Then, we have
the following error bounds.  

\begin{lemma} \label{lem:logic_bounds}
Assuming node $X$ plays itself with weight $v_1'$, $v_1 - \epsilon_l \leq v_1' \leq v_1 + \epsilon_l$, and node $Y$ plays itself with weight $v_2'$, $v_2 - \epsilon_l \leq v_2' \leq v_2 + \epsilon_l$, each of the boolean gadgets plays itself within $\pm (2\epsilon_l + 6\epsilon)$ of the correct value for the correct $v_1$ and $v_2$ inputs.
\end{lemma}

\begin{proof}
\subsubsection*{OR}
%\BfPara{OR}
If $v_1$ and/or $v_2$ is 1, then $v_1'$ and/or $v_2'$ is at least $1 -
\epsilon_l$, and node $R_1$ will play $R_1$ with weight at most
$\epsilon_l + \epsilon$, so $R$ will play $R$ with weight at least
$1 - \epsilon_l - 2\epsilon$. If both $v_1$ and $v_2$ are 0, then
$v_1'$ and $v_2'$ are at most $\epsilon_l$, and node $R_1$ will play
$R_1$ with weight at least $1 - 2\epsilon_l - 2\epsilon$, so $R$ will
play $R$ with weight at most $2\epsilon_l + 3\epsilon$.
%\\
%\BfPara{NOT} 
\subsubsection*{NOT}
If $v_1 = 1$, $v_1'$ is at least $1-\epsilon_l$, and node $N$ will
play itself with weight at most $\epsilon_l + \epsilon$. If $v_1 =
0$, $v_1'$ is at most $\epsilon_l$, and node $N$ will play $N$ with
weight at least $1 - \epsilon_l - \epsilon$.
%\\
%\BfPara{AND} 
\subsubsection*{AND}
The AND gadget concatenates other new players to
get $\lnot(\lnot v_1 \lor \lnot v_2)$. Each NOT may add at most one
additional $\epsilon$ error to the given value, and the OR may add up
to $3\epsilon$ error (on top of the sum of the errors from both
inputs). So the AND player will return a value within an additive
$2 \epsilon_l + 6\epsilon$ of the correct 0 or 1 answer.
\end{proof}

\begin{lemma} \label{lem:arith_bounds}
Each of the arithmetic gadgets plays itself within $\pm 5\epsilon$ of the correct value for the input it is given.
\end{lemma}

\begin{proof}
%\BfPara{SUM} 
\subsubsection*{SUM}
Node $S_1$ will play $S_1$ with weight $w(S_1T) \in [max(0,
1-v_1'-v_2'-2\epsilon), max(0, 1-v_1'-v_2' + 2\epsilon)]$. So node $S$
will play $S$ with weight $w_S(S) \in [v_1' + v_2' - 3\epsilon, v_1' +
v_2' + 3\epsilon]$, unless $w_{S_1}(S_1)=0$, which means $v_1' + v_2'
\geq 1 - 2\epsilon$. In this case, node $S$ will play $S$ with
weight at least $1 - \epsilon$.
%\\
%\BfPara{DIFF} 
\subsubsection*{DIFF}
Node $D_1$ will play $D_1T$ with weight $w_{D_1}(D_1) \in max(0, 1 - v_1' -
\epsilon), max(0, 1 - v_1' + \epsilon)]$. Node $D$ will play $D$ with
weight $w_D(D) \in [max(0, v_1' - v_2' - 3\epsilon), max(0, v_1' - v_2'
+ 3\epsilon)]$, unless $w_{D_1}(D_1)=0$ which means $v_1' \geq 1 -
\epsilon$. In this case, node $D$ will play $D$ with weight at least
$1 - v_2' - 2\epsilon$ and at most $1 - v_2' + \epsilon$ (not
$2\epsilon$ because we cannot underfill the strategy with weight 0).
%\\
%\BfPara{COPY} 
\subsubsection*{COPY}
Node $C_1$ will play $C_1$ with weight at least $1 - v_1' - \epsilon$
and at most $1 - v_1' + \epsilon$. Node $C$ will play $C$ with weight
at least $v_1' - 2\epsilon$ and at most $v_1' + 2\epsilon$.
%\\
%\BfPara{HALF} 
\subsubsection*{HALF}
Node $H_1$ will play $H_1$ with weight $w_{H_1}(H_1) \in [1 - v_1' -
\epsilon, 1 - v_1' + \epsilon]$, and each other player will play its
second and third preferences with total weight between $1 -
w_{H_1}(H_1) - \epsilon$ and $1 - w_{H_1}(H_1) + \epsilon$. Each other
player will play itself half of this amount plus or minus $3\epsilon$
(this is easy to verify by writing the system of inequalities and
checking the extreme points). Therefore, node $H$ plays $H$ with
weight at least $\frac{v_1'}{2} - 4\epsilon$ and at most
$\frac{v_1'}{2} + 4\epsilon$.
%\\
%\BfPara{DOUBLE}
\subsubsection*{DOUBLE}
The DOUBLE gadget consists of a copy player, which adds at most
$2\epsilon$ error, and a sum player, which adds at most $3\epsilon$
error on top of the sum of the errors in the two inputs. Therefore,
node $M$ plays $M$ with weight at least $2v_1' - 5\epsilon$ and at
most $2v_1' + 5\epsilon$.
\end{proof}

\begin{lemma} \label{lem:lt_bounds}
The LESS player will play itself with weight $< \epsilon_l$ if it is given $v_1', v_2'$ such that $v_1' \leq v_2'$, and with weight $> 1 - \epsilon_l$ if $v_1' - v_2' \geq \epsilon_l$.
\end{lemma}

\begin{proof}
\subsubsection*{LESS}
%\BfPara{LESS} 
The LESS gadget inherits its susceptibility to error from its
initial DIFF player (which was, in the exact equilibrium case,
non-zero if and only if $v_1 < v_2$). For the case where $v_1 < v_2$,
we can account for the errors of the DOUBLE players (used to
repeatedly amplify the difference) simply by adding extra iterations
of DOUBLE. Since we stipulated that $\epsilon \leq
\epsilon_l^3$, a value that started $\leq 5\epsilon$ will remain $<
\epsilon_l$, even after doubling enough times to push a value
$\geq \epsilon_l$ to a value over 1 (including extra multiplications
to account for the DOUBLE errors). Therefore, the LESS player will
play itself with weight less than $\epsilon_l$ if $v_1' \leq v_2'$ and
with weight greater than $1 - \epsilon_l$ if $v_1' - v_2' \geq
\epsilon_l$.
\end{proof}
\smallskip


\junk{
Next, we generate another gadget that can be used to amplify the
results of each boolean logic player before using it, in order to
ensure that each input within the circuit is close to the correct
value.  
\subsubsection*{CORRECTION} 
}

\begin{lemma}
\label{lem:correction}
By using a LESS gadget after each boolean logic gadget, we can ensure that the output from each gate is at most $\epsilon_l$ away from the correct output.
\end{lemma}
\begin{proof}
After a single gate (if the inputs are
within additive $\epsilon_l$ of the correct 0 or 1 inputs), a player
will play itself at least $1 - 2\epsilon_l - 6\epsilon$ if the correct
answer is $1$, and at most $2\epsilon_l + 6\epsilon$ if the correct
answer is $0$ (based on the analysis in the proof of
Lemma ~\ref{lem:logic_bounds}). Call this player OUTPUT and the value it plays itself $v$.  
Then, we only need to add a player CONSTANT-HALF who plays itself with weight close to $\frac{1}{2}$, and a LESS
player, CORRECTION $=$ LESS(OUTPUT, CONSTANT-HALF). 

CONSTANT-HALF can be made up of a player who plays itself with weight at least $1 - \epsilon$ and at most $1$ (its first preference is for itself) and a HALF player, who by Lemma \ref{lem:arith_bounds} will play itself with weight at least $\frac{1 - \epsilon}{2} - 5\epsilon$ and at most $\frac{1}{2} + 5\epsilon$.

We know that if the correct answer was $0$, then $v \leq 2\epsilon_l + 6\epsilon < \frac{1 - \epsilon}{2} - 5\epsilon$, so CORRECTION will play itself with weight $< \epsilon_l$ (by Lemma \ref{lem:lt_bounds}), and if the correct answer was $1$, then $v \geq 1 - 2\epsilon_l - 6\epsilon > \frac{1}{2} + 5\epsilon + \epsilon_l$, so CORRECTION will play itself with weight $> 1 - \epsilon_l$ (again by Lemma \ref{lem:lt_bounds}).   
\end{proof}

After the corrections, we're left with the following possible errors
due to the $\epsilon$-approximation. We have small errors in the bit
extraction, which are no larger than the parallel errors
in~\cite{DaskalakisGoldbergPapadimitriou06} (they verify that these
small error values will not affect the final result). We also have
small errors (at most $\epsilon_l$) coming out of the circuit. As
in~\cite{ChenDengTeng06,ChenDengTeng08}, we will repeat the circuit a
polynomial number of times and take the average in order to override
any errors from the LESS gadgets in the bit extraction.  

Taking an average of two results requires 3 steps: first
we divide each ``bit'' in half (we cannot take the average of the
entire values because we have a max value of 1 for any player, so the
average of two 1's would come out to $\frac{1}{2}$). Here, we may pick
up $4\epsilon$ of error for each of the two results. Then, we sum the
two. The total error so far is at most $11\epsilon$. Finally, we take
half of the sum, which also divides the error in half, but may add up
to an additional $4\epsilon$ of error, for a total additional error of
at most $9.5\epsilon$ from taking the average of 2 results.  

We can add LESS gadgets periodically during the averaging and
during the final OR, AND and NOT of the results to keep our total
errors under $\epsilon_l$. In other words, if this is a solution
vertex for \brouwer, then we will have 6 players, each playing at most
$\epsilon_l$. If this is not a solution vertex, then at least one of
the 6 players will play at least $1 - \epsilon_l$.  

Suppose we have an $\epsilon$-equilibrium in this game, and the
x-coordinate player is playing value $x$. This is a SUM player, and
the extra player from the SUM gadget must be playing between
$1-x-\epsilon$ and $1-x+\epsilon$. Therefore, the sum of the two
values it is adding (a copy of the coordinate player and the feedback
NOT player) must be between $x-3\epsilon$ (if this player overfills
each of its top strategies by $\epsilon$) and $x+3\epsilon$ (if this
player underfills each of its top strategies by $\epsilon$). We know
that the copy player must be playing the same value as the coordinate
player to within $2\epsilon$ (between $x-2\epsilon$ and
$x+2\epsilon$). Adding this range to a number $\geq 1 - \epsilon_l$
cannot possibly give something in the range $[x-3\epsilon,
x+3\epsilon]$, so the feedback player must be playing a value at most
$\epsilon_l$ on itself (since we know the feedback player will play
either a value $\leq \epsilon_l$ or a value $\geq 1-\epsilon_l$),
and the correct feedback must be 0, so this is a valid fixed point.
